package leetcode;

public class Leetcode5 {
    public String longestPalindrome(String s) {
        if(s.length()==0||s.length()==1){
            return s;
        }
        String max = "";
        for (int i = 0; i < s.length()-1; i++) {
            String s1 = palindromeString(s,i,i);
            String s2 = palindromeString(s,i,i+1);
            String maxString = s1.length()>s2.length()?s1:s2;
            max = maxString.length()>max.length()?maxString:max;
        }
        return max;
    }

    public String palindromeString(String s,int start,int end){
        while(start>=0&&end<s.length()){
            if(s.charAt(start)==s.charAt(end)){
                start--;
                end++;
            }else{
                break;
            }
        }
        return s.substring(start+1,end);
    }

    public String longestPalindrome1(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }
        int max = 1;
        int begin = 0;
        String maxS = "";
        boolean[][] dp = new boolean[len][len];
        for(int i = 0;i < len;i++){
            dp[i][i] = true;
        }
        for(int j = 1;j<len;j++){
            for(int i = 0;i<j;i++){
                if(s.charAt(i)!=s.charAt(j)){
                    dp[i][j] = false;
                }else{
                    if(j-i<3){
                        dp[i][j] = true;
                    }else{
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
                if(dp[i][j]==true){
                    if(j-i+1>max){
                        max = j-i+1;
                        begin = i;
                    }
                }
            }
        }
        return s.substring(begin,begin+max);
    }
}
